package com.benben.springSecurity.weiwei;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//全排列，回溯搜索+状态重置
public class AllPailie {
    public List<List<Integer>> permute(int[] nums){
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[len];
        if(len == 0){
            return res;
        }
        generatePermution(nums,used,0,len,new Stack<>(),res);
        return res;
    }
    private void generatePermution(int[] nums,boolean[] visited,int curSize,int len,Stack<Integer> path,List<List<Integer>> res){
        if(curSize == len){
            //此时path已经保存了nums中的所有数字，已经成为了一个排列
            res.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<len;i++){
            if(!visited[i]) {
                path.push(nums[i]);
                visited[i] = true;
                generatePermution(nums,visited,curSize+1,len,path,res);
                //回溯的时候一定要记得状态重置
                path.pop();
                visited[i] = false;
            }
        }
    }
}
